<template>
    <MyArticle title="Java学习笔记之七：集合(1)" date="2024年03月13日">
        <div class="_article-content">
            <p>Java集合类库也将接口与实现分离。集合类的基本接口是Collection接口：</p>
            <pre><code>public interface Collection&lt;E&gt;{
    boolean add(E element);
    Iterator&lt;E&gt; iterator();
}</code></pre>
            <p>add方法用于向集合中添加元素，如果添加元素确实改变了集合就返回true，如果集合没有发生变化就返回false。iterator方法用于返回一个实现了Iterator接口的对象。可以使用这个迭代器对象依次访问集合中的元素。</p>
            <p>Iterator接口包含4个方法：</p>
            <pre><code>public interface Iterator&lt;E&gt;{
    boolean hasNext();
    E next();
    void remove();
    default void forEachRemaining(Consumer&lt;? super E&gt; action);
}</code></pre>
            <p>在调用next之前需要调用hasNext方法：</p>
            <pre><code>Collection&lt;String&gt; c = ....;
Iterator&lt;String&gt; it = c.iterator();
while(it.hasNext()){
    String s = it.next();
    //do something
}</code></pre>
            <p>也可以使用for each循环：</p>
            <pre><code>for (String element : c){ do something }</code></pre>
            <p>对于标准类库中的任何集合都可以使用for each循环。</p>
            <p>也可以调用forEachRemaining方法并提供一个lambda表达式，将对迭代器的每一个元素调用这个lambda表达式，直到再没有元素为止：</p>
            <pre><code>iterator.forEachRemaining(element -&gt; do something);</code></pre>
            <p>Iterator接口的remove方法会删除上次调用next方法返回的元素。调用remove之前没有调用next，将是不合法的，如果这样做，会抛出一个IllegalStateException异常。</p>
            <pre><code>ArrayList&lt;String&gt; arr = new ArrayList&lt;String&gt;();
                Iterator iterator = arr.iterator();
arr.add("a1");
arr.add("b2");
iterator.next();
iterator.remove(); //将删除a1</code></pre>
            <p>Collection接口中的其他方法：</p>
            <pre><code>int size();
boolean isEmpty();
boolean contains(Object o);
boolean containsAll(Collection&lt;?&gt; c);// 如果这个集合中包含other集合中的所有元素，返回true
boolean equals(Object other);
boolean addAll(Collection&lt;? extends E&gt; c);
boolean remove(Object o); // 从这个集合中删除等于o的对象，如果有匹配的对象被删除，返回true
boolean removeAll(Collection&lt;?&gt; c);
void clear();
boolean retainAll(Collection&lt;?&gt; other);// 从这个集合中删除所有与other集合中元素不同的元素
Object[] toArray();
boolean removeIf(Predicate&lt;? spuer E&gt; filter); // 从这个集合删除让filter返回true的所有元素</code></pre>
            <p>集合框架中的接口继承关系：</p>
            <figure class="common">
                <a class="pswp-img" href="https://gitee.com/bravelin/pics/raw/master/article/202503130839.webp" data-pswp-width="1077" data-pswp-height="848" target="_blank">
                    <img class="thumbnail-img" src="https://gitee.com/bravelin/pics/raw/master/article/202503130839.webp"/>
                </a>
            </figure>
            <p>Map包含键/值对，要用put方法在Map中添加元素：</p>
            <pre><code>V put(V key, V value);</code></pre>
            <p>List是一个有序集合；Set接口等同于Collection，但Set的add方法不允许增加重复的元素。</p>
            <p>Java类库中的具体集合：</p>
            <table class="inner-table">
                <thead>
                    <tr><th style="width:20%">类型</th><th>描述</th></tr>
                </thead>
                <tbody>
                    <tr><td>ArrayList</td><td>可以动态增氏和缩减的一个索引序列</td></tr>
                    <tr><td>LinkedList</td><td>可以在任意位置高效插入和删除的一个有序序列</td></tr>
                    <tr><td>ArrayDeque</td><td>实现为循环数组的一个双端队列</td></tr>
                    <tr><td>HashSet</td><td>没有重复元素的一个无序集合</td></tr>
                    <tr><td>TreeSet</td><td>一个有序集</td></tr>
                    <tr><td>EnumSet</td><td>一个包含枚举类型值的集</td></tr>
                    <tr><td>LinkedHashSet</td><td>一个可以记住元素插入次序的集</td></tr>
                    <tr><td>PriorityQueue</td><td>允许高效删除最小元素的一个集合</td></tr>
                    <tr><td>HashMap</td><td>存储键/值关联的一个数据结构</td></tr>
                    <tr><td>TreeMap</td><td>键有序的一个映射</td></tr>
                    <tr><td>EnumMap</td><td>键属于枚举类型的一个映射</td></tr>
                    <tr><td>LinkedHashMap</td><td>可以记住键/值项添加次序的一个映射</td></tr>
                    <tr><td>WeakHashMap</td><td>这个映射中的值如果不在别处使用，就会被垃圾回收器回收</td></tr>
                    <tr><td>IdentityHashMap</td><td>用==而不是用equals比较键的一个映射</td></tr>
                </tbody>
            </table>
            <p>以Map结尾的类实现了Map接口，其他类都实现了Collection接口。</p>
            <figure class="common">
                <a class="pswp-img" href="https://gitee.com/bravelin/pics/raw/master/article/202503130914.webp" data-pswp-width="839" data-pswp-height="901" target="_blank">
                    <img class="thumbnail-img" src="https://gitee.com/bravelin/pics/raw/master/article/202503130914.webp"/>
                </a>
            </figure>
            <h3 class="title">LinkedList类</h3>
            <p>在Java程序设计语言中，所有链表实际上都有双向链接（doubly linked），即每个链接存储着其前驱和后驱的引用。</p>
            <p>LinkedList是一个有序集合，LinkedList.add方法将对象添加到链表的尾部；如果需要在中间添加元素，需要使用ListIterator接口：</p>
            <pre><code>LinkedList staff = new LinkedList&lt;String&gt;();
staff.add("Amy");
staff.add("Bob");
staff.add("Carl");
ListIterator&lt;String&gt; iterator = staff.listIterator();
iterator.next();
iterator.add("Dave"); // Amy、Dave、Bob、Carl</code></pre>
            <p>ListIterator接口有两个方法可以用来反向遍历链表：</p>
            <pre><code>E previouse();
boolean hasPrevious();</code></pre>
            <p>ListIterator接口的set方法会用一个新元素替换调用next或者previous方法返回的上一个元素：</p>
            <pre><code>ListIterator&lt;String&gt; iterator = staff.listIterator();
iterator.next();
iterator.set("cycle");</code></pre>
            <p>如果一个迭代器发现它的集合被另一个迭代器修改了，或是被该集合后身的某个方法修改了，就会抛出一个ConcurrentModificationException异常。</p>
            <p>LinkedList类提供了一个get方法，用来访问某个特定元素，但效率不高：</p>
            <pre><code>LinkedList staff = new LinkedList&lt;String&gt;();
......
String str = staff.get(n);</code></pre>
            <p>使用链表的唯一理由是尽可能地减少在列表中间插入或删除元素的开销。</p>
            <p>iterator的指向顺序不会动态改变：</p>
            <pre><code>LinkedList&lt;String&gt; arr1 = new LinkedList&lt;String&gt;();
arr1.add("a");
arr1.add("b");
arr1.add("c");
ListIterator&lt;String&gt; iterator1 = arr1.listIterator();

LinkedList&lt;String&gt; arr2 = new LinkedList&lt;String&gt;();
arr2.add("u");
arr2.add("p");
arr2.add("w");
arr2.add("z");
ListIterator&lt;String&gt; iterator2 = arr2.listIterator();

while (iterator2.hasNext()) {
    if (iterator1.hasNext()) {
        iterator1.next();
    }
    iterator1.add(iterator2.next());
}
System.out.println(arr1.toString()); // [a, u, b, p, c, w, z]</code></pre>
            <h3 class="title">ArrayList类</h3>
            <p>ArrayList封装了一个动态再分配的对象数组。Vector类的所有方法都是同步的，可以安全地从两个线程访问一个Vector对象，ArrayList方法是不同步的，不需要同步时建议使用ArrayList。</p>
            <h3 class="title">散列集</h3>
            <p>散列表为每个对象计算一个整数，称为散列码（hash code）。散列码是以某种方式由对象的实例字段得出的一个整数，这种方式可以尽可能保证有不同数据的对象将生成不同的散列码。</p>
            <p>散列表实现为链表数组，每个列表被称为桶。要想查找一个对象在表中的位置，就要先计算它的散列码，然后与桶的总数取余, 所得到的数就是保存这个元素的那个桶的索引。如果桶中没有其他元素，此时将元素直接插人这个桶中就可以了，有时候会遇到桶已经填充了元素的情况，这种现象被称为散列冲突。需要将新对象与那个桶中的所有对象进行比较，查看这个对象是否已经存在。</p>
            <figure class="common">
                <a class="pswp-img" href="https://gitee.com/bravelin/pics/raw/master/article/202503131107.webp" data-pswp-width="567" data-pswp-height="432" target="_blank">
                    <img class="thumbnail-img" src="https://gitee.com/bravelin/pics/raw/master/article/202503131107.webp"/>
                </a>
            </figure>
            <p>散列表的键要尽可能属于一个实现了Comparable接口的类，就能保证不会由于散列码分布不均而导致性能低下。</p>
            <p>可以指定一个初始的桶数，桶数是指用于收集有相同散列值的桶的数目，如果要插入到散列表中的元素太多，冲突数就会增加，这会降低检索性能。</p>
            <p>通常，要将桶数设置为预计元素个数的75%~150%。如果散列表太满，就需要再散列（rehashed）：创建一个桶数更多的表，并将所有元素插人这个新表中，然后丢弃原来的表。装填因子可以确定何时对散列表进行再散列。如果装填因子为0.75（默认值），而表中已经填满了75%以上，就会自动再散列，新表的桶数是原来的两倍。</p>
            <p>集是没有重复元素的元素集合。集的add方法首先尝试在这个集中查找要添加的对象，只有这个元素不存在时才会添加这个对象。</p>
            <pre><code>var words = new HashSet&lt;String&gt;();</code></pre>
            <p>TreeSet类与散列集十分类似，不过，它比散列集有所改进。树集是一个有序集合，可以以任意顺序将元素插入集合中。在对集合进行遍历时，值将自动地按照排序后的顺序出现。</p>
            <pre><code>TreeSet&lt;String&gt; arr1 = new TreeSet&lt;String&gt;();
arr1.add("Bob");
arr1.add("Amy");
arr1.add("Carl");
System.out.println(arr1.toString()); // [Amy, Bob, Carl]</code></pre>
            <p>排序是用红黑树数据结构完成的。每次将一个元素添加到树中时，都会将其放置在正确的排序位置上，因此，迭代器总是以有序的顺序访问每个元素。</p>
            <p>将一个元素添加到树中要比添加到散列表中慢，但是，与检查数组或链表中的重复元素相比，使用树还是会快得多。如果树中包含n个元素，查找新元素的正确位置平均需要log<sub>2</sub>N次比较。</p>
            <h3 class="title">队列</h3>
            <p>队列允许高效地在队尾添加元素，并在队头删除元素。双端队列在队头和队尾都能高效地添加或删除元素。不支持在队列中问添加元素。ArrayDeque和LinkedList类实现了Deque接口，这两个类都可以提供双端队列，其大小可以根据需要扩展。</p>
            <p>优先队列中的元素可以按照任意的顺序插入，但会按照有序的顺序获取。也就是说，调用remove方法时，总会获得当前优先队列中最小的元素。内部利用了堆这种数据结构。堆是一个自组织的二叉树，其添加和删除操作会让最小的元素移动到根。</p>
            <p>优先队列的典型用法是任务调度。每一个任务有一个优先级，任务以随机顺序添加到队列中，每当启动一个新的任务时，将从队列中删除优先级最高的任务。</p>
            <pre><code>PriorityQueue&lt;LocalDate&gt; arr1 = new PriorityQueue&lt;LocalDate&gt;();
arr1.add(LocalDate.of(1988, 4, 20));
arr1.add(LocalDate.of(1980, 2, 20));
arr1.add(LocalDate.of(1990, 1, 20));
arr1.add(LocalDate.of(1950, 1, 20));
System.out.println(arr1.toString());
while (!arr1.isEmpty()) {
    System.out.println(arr1.remove()); // 依次输出：1950-01-20, 1980-02-20, 1988-04-20, 1990-01-20
}</code></pre>
            <h3 class="title">映射</h3>
            <p>映射用来存放键/值对，如果提供了键，可以查找一个值。HashMap散列映射对键进行散列，TreeMap树映射根据键的顺序将它们组织为一个搜索树。散列或比较函数只应用于键，与键关联的值不进行散列或比较。</p>
            <p>如果不需要按照有序的顺序访问键，最好选择散列映射。</p>
            <pre><code>var staff = new HashMap&lt;String, Employee&gt;();
var lucy = new Employee("Lucy", 10000);
staff.put("999-098-187", lucy);

String id = "999-098-187";
Employee e = staff.get(id);</code></pre>
            <p>如果映射中没有存储与指定键对应的信息，get将返回null。</p>
            <p>有时对于没有出现在映射中的键，可以有一个合适的默认值，可以使用getOrDefault：</p>
            <pre><code>Map&lt;String, Integer&gt; scores = ...
int score = scores.getOrDefault(name, 0);</code></pre>
            <p>键必须是唯一的，不能对同一个键存放两个值。如果用同一个键调用两次put方法，第二个值就会取代第一个值。remove方法从映射中删除给定键对应的元素，size方法返回映射中的元素数。</p>
            <p>迭代处理映射的键和值：</p>
            <pre><code>scores.forEach((k, v) -&gt; System.out.print("key=" + k + ",value=" + v));</code></pre>
            <p>映射视图：键集、值集合、以及键值对集：</p>
            <pre><code>Set&lt;K&gt; keySet();
Collection&lt;V&gt; values();
Set&lt;Map.Entry&lt;K, V&gt;&gt; entrySet();</code></pre>
            <p>枚举一个映射的所有键：</p>
            <pre><code>Set&lt;String&gt; keys = map.keySet();
for (String key : keys) {
    System.out.println(key);
}</code></pre>
            <p>枚举键值对集：</p>
            <pre><code>for (Map.Entry&lt;String, Employee&gt; entry : staff.entrySet()){
    String k = entry.getKey();
    Employee v = entry.getValue();
    System.out.println("key=" + k + ",value=" + v);
}</code></pre>
            <p>可以从键值对集中删除元素，所删除的元素也将从映射中删除，但是不能添加任何元素。</p>
            <p>WeakHashMap使用弱引用保存键，WeakReference对象将包含另一个对象的引用，如果垃圾回收器发现某个特定的对象已经没有引用了，就会将其回收。</p>
            <p>LinkedHashSet和LinkedHaspMap类会记住插入元素项的顺序，这样可以避免散列表中看起来随机的元素顺序。在散列表中插人元素项时，它们会加人一个双向链表中。</p>
            <p>EnumSet是一个高效的集实现, 其元素属于一个枚举类型。因为枚举类型只有有限个实例，所以在内部实现为一个位序列。EnumSet类没有公共构造器，要使用静态工厂方法构造这个集：</p>
            <pre><code>enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet&lt;Weekday&gt; set = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
EnumSet&lt;Weekday&gt; set = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);</code></pre>
            <p>EnumMap是一个映射，它的键属于一个枚举类型，EnumMap可以简单高效地实现为一个值数组，需要在构造器中指定键类型：</p>
            <pre><code>var personInCharge = new EnumMap&lt;Weekday, Employee&gt;(Weekday.class);</code></pre>
            <p>IdentityHashMap键的散列值不是用hasCode函数计算的，而是用System.identityHashCode方法计算的。对两个对象进行比较时，IdentityHashMap使用了==，而不是equals。也就是说，不同的键对象即使内容相同，也被视为不同的对象。</p>
        </div>
    </MyArticle>
</template>
